# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/23 15:34
@FileName      : 计数排序.py
@LastEditors   : None
@Editors       : PyCharm
"""
# 复杂度O(max+n)
# 不稳定
'''占用多余内存，不建议使用'''
'''不重要，但是可以学习里面的一些算法思维'''
arr = [4, 2, 2, 8, 3, 3, 1]


def counting_sort(arr):
    # 找到最大值
    max = arr[0]
    for i in arr:
        if max < i:
            max = i
    counting_list = [0] * (max + 1)
    output_list = [0] * len(arr)
    # 累加出现次数
    for i in arr:
        counting_list[i] += 1
    # 根据出现次数找到元素位置
    for i in range(1, max + 1):
        counting_list[i] += counting_list[i - 1]
    # 根据counting_list中的信息，将arr数组中的元素储存在output_list中
    for i in arr:
        output_list[counting_list[i] - 1] = i
        counting_list[i] -= 1
    # 将output_list中的元素拷贝在arr中
    for i in range(len(arr)):
        arr[i] = output_list[i]


counting_sort(arr)
print(arr)
